The present invention relates to providing a digital fingerprint for an electronic document.
Due to the rapid growth of the Internet and the possibility to digitally distribute documents, there is an increasing need to protect against illegal distribution of documents and thus to protect copyright holders against pirated copies.
For this purpose, large corporations like IBM, NEC and Microsoft, and also smaller companies like Digimarc (see Funkschau 17/97; p. 21) and research institutes such as the Fraunhofergesellschaft IGD and GMD Darmstadt are working on imbedding digital watermarks in documents. In processes based on this principle, a piece of information that identifies the copyright holder is invisibly inserted into the documents to be protected. The type of digital watermark inserted depends on the particular type of document (e.g., PostScript, JPEG, MPEG-1).
Digital watermarks allow the copyright holder to ascertain its intellectual property in an illegally distributed document.
Digital watermarks, however, do not make it possible to identify the person responsible for illegal distribution or to prove that that person is responsible for the illegal distribution.
Digital fingerprints go one step further. In using the principle of securing a document using digital fingerprints, the name of the customer who purchases an electronic copy of the document is invisibly inserted into the document in addition to the digital watermark of the copyright holder. Should this customer further distribute his copy contrary to the interests of the copyright holder, he can be uniquely identified and held liable using his electronic fingerprint contained in all illegal copies. (Dan Boneh and James Shaw: Collusion-Secure Fingerprinting for Digital Data, Proc. CRYPTO xe2x80x9c95xe2x80x9d LNCS 963, Springer Verlag, Berlin 1995, 452-465.)
The principle of securing documents using digital fingerprints has so far had one serious weakness resulting from the fact that the documents assigned to individual customers differ in their bit patterns exactly at the location where the individual user-specific fingerprint of the different customers is located. If a customer comes into possession of the document of a second customer, he can trace the locations with the different digital fingerprints by comparing the two documents bit by bit and remove (delete) those locations from the document. The object of such a manipulation is always to obtain a copy of the document from which the user-specific fingerprints have been removed.
An object of the present invention is to eliminate this shortcoming. As previously, each document should be assigned to one customer only. The customers should not be capable, either individually or as a group, of deleting all the customer-specific fingerprints. Furthermore, the present invention helps make it possible to determine without doubt, from the still remaining fragments of the digital fingerprints of an illegally distributed document, which customers or which documents were involved in the manipulation. Customers involved in such manipulations are henceforth referred to as hackers.
The present invention provides a method of inserting manipulation-proof digital fingerprints into electronic documents, in which each purchaser is assigned a copy of a document in which an individual fingerprint, assigned to the respective purchaser of the copy, which is not recognizable by the purchaser, is inserted as a marking. The present invention is characterized in that the marking locations of the individual digital fingerprint that is different for each copy are assigned using finite geometric structures, the copy of each purchaser being marked at locations determined by the geometric substructure assigned to the respective customer and a secret function. The points thus established for each purchaser as a digital fingerprint are determined within the geometric structure so that they intersect with fingerprint points of other purchasers; and, using bit-by-bit comparison of the original document with a copy from which parts of fingerprints have been removed by manipulation of at most d purchasers, copies involved in the manipulation and thus the purchasers acting as hackers are identified from the set of fingerprint intersections still present.
With the present invention, a hacker in comparing documents of different customers may be able discover the locations where the fingerprints differ, but he cannot identify those locations in both documents where the fingerprints are identical.
According to the present invention, a location or an area for the digital fingerprint of the customer is defined for each copy from a predetermined number of copies of the document. All the locations and areas defined in the document for the digital fingerprints are subject, in their totality, to an enclosed finite ordering system, in which intersections of the digital fingerprints are defined at exactly defined locations or areas. In the case of a digital fingerprint place assignment performed according to this principle, all locations or areas S, where digital fingerprints intersect, cannot be identified by the customers whose digital fingerprints intersect at location or area S. If the number of hackers does not exceed the number of hackers allowed by the system, the hackers involved in the manipulation can be uniquely identified using a comparison of the document with the manipulated copy, based on the analysis of the intersection points not found by the hackers.
According to the present invention, the fingerprints are placed on the basis of finite geometric structures, with a unique place of the selected finite geometric structure being assigned to each individual point of a fingerprint. Clearly defined areas, which can be deduced from the geometric structure, such as intersection points, for example, where digital fingerprints intersect according to the assignment of the individual digital fingerprints, are defined within the finite geometric structure. These areas, referred to as points of intersection S, cannot be identified by the customers whose digital fingerprints intersect at these locations or areas S. In the case of manipulation, it is to be assumed that the hackers will generally not succeed in deleting all the points or areas of intersection.
Based on the geometric regularities existing in finite geometric structures, the customers involved in the manipulation as hackers can be identified using the points or areas of intersection that they did not identify.
Dual rational normal curves in finite projective planes or dual rational normal curves in finite projective spaces can be used, for example, as finite geometric structures in the context of the present invention.
The use of dual rational normal curves in projective spaces is particularly recommended when copies of the document have to be distributed to a large number of customers.